package com.xzx.algorithms.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * 给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
 * 输入: s = "abcabcbb"
 * 输出: 3
 * 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
 *
 * @author xinzhixuan
 * @version 1.0
 * @date 2025/2/5 16:21
 */
public class D0003_MaxLengthSubString {
    public static void main(String[] args) {
        System.out.println(lengthOfLongestSubstring3("au"));
    }

    /**
     * 思路是判断比较子字符串是否包含当前字符，如果不包含则追加到子串中，如果包含则需要从子串中找到该字符的位置，然后将该位置之前的所有内容删除。
     *
     * @param s .
     * @return .
     */
    private static int lengthOfLongestSubstring(String s) {
        StringBuilder maxSub = new StringBuilder();// 最长子串 这个会占用较大的空间
        StringBuilder currentSub = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            if (currentSub.toString().contains(String.valueOf(s.charAt(i)))) {
                currentSub = new StringBuilder(currentSub.substring(currentSub.indexOf(String.valueOf(s.charAt(i))) + 1));
            }
            currentSub.append(s.charAt(i));
            if (currentSub.length() > maxSub.length()) {
                maxSub = currentSub;
            }
        }
        System.out.println(maxSub);
        return maxSub.length();
    }

    /**
     * 方法1中出现大量的子字符串，所以对空间占用也是比较大的，所以可以使用滑动窗口的方式来优化
     *
     * @param s .
     * @return .
     */
    private static int lengthOfLongestSubstring2(String s) {
        Set<Character> set = new HashSet<>();
        int right = 0, length = 0;
        for (int i = 0; i < s.length(); i++) {
            while (right < s.length() && !set.contains(s.charAt(right))) {
                set.add(s.charAt(right));
                right++;
            }
            // right执行完一次，left也就是i删除一次字符，因为set中总是不重复的字符
            set.remove(s.charAt(i));

            length = Math.max(length, right - i);
        }
        return length;
    }

    /**
     * 因为字符的本质是ascii码，长度最大也就是128，所以可以直接用循环来代替hash去重
     * @param s
     * @return
     */
    private static int lengthOfLongestSubstring3(String s) {
        int left = 0, length = 0, max = 0;
        for (int right = 0; right < s.length(); right++) {
            for (int k = left; k < right; k++) {
                if (s.charAt(k) == s.charAt(right)) {
                    left = k + 1;
                    break;
                }
            }
            length = right - left;
            max = Math.max(length + 1, max);
        }
        return max;
    }
}
